package dynamicProgramming;

import java.util.Arrays;

public class Dp {
	//不用装满
	public static int fun1(int V,int n,int[] v,int[] w) {
		int[][] dp=new int[n+1][V+1];
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=V;j++) {
				dp[i][j]=dp[i-1][j];
				if(j-v[i-1]>=0)
					dp[i][j]=Math.max(dp[i][j],w[i-1]+dp[i-1][j-v[i-1]]);
			}
		}
		return dp[n][V];
	}
	//需要装满
	public static int fun2(int V,int n,int[] v,int[] w) {
		int[][] dp=new int[n+1][V+1];
		Arrays.fill(dp[0],-1);
		dp[0][0]=0;
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=V;j++) {
				dp[i][j]=dp[i-1][j];
				if(j-v[i-1]>=0&&dp[i-1][j-v[i-1]]!=-1)
					dp[i][j]=Math.max(dp[i][j],w[i-1]+dp[i-1][j-v[i-1]]);
			}
		}
		return dp[n][V]==-1?0:dp[n][V];
	}
	public static void main(String[] args) {
		int[] v1=new int[] {2,4,1};
		int[] w1=new int[] {10,5,4};
		System.out.println(fun1(5,3,v1,w1));
		System.out.println(fun2(5,3,v1,w1));
		int[] v2=new int[] {12,11,6};
		int[] w2=new int[] {6,8,8};
		System.out.println(fun1(8,3,v2,w2));
		System.out.println(fun2(8,3,v2,w2));
		
	}
}
